import os
import sys
import struct
import bon

class SplayDictFile(object):
	def __init__(self, filename, iterable=None, root_pos=0):
		self._filename = filename
		self._root_pos = root_pos
		
		if os.path.exists(self._filename):
			# file
			self._f = open(self._filename, 'rb+')
			
			# root
			self._f.seek(self._root_pos, 0)
			pos, = struct.unpack('!Q', self._f.read(8))
			
			if pos == 0:
				self._root = None
			else:
				self._root = _SplayDictFileEntry(self._f, pos, None, None, None, None)
				self._root.read()
		else:
			# file
			self._f = open(self._filename, 'wb+')
			
			# root
			self._f.seek(self._root_pos, 0)
			self._f.write(struct.pack('!Q', 0))
			self._root = None
		
		# header
		self._f.seek(0, 2)
		header_pos = self._f.tell()
		self._header = _SplayDictFileEntry(self._f, header_pos, self._root_pos, self._root_pos, self._root_pos, self._root_pos)
		self._header.write()
		
		#
		# update with iterable
		#
		if isinstance(iterable, dict):
			for k, v in iterable.items():
				self[k] = v
		elif iterable:
			for k, v in iterable:
				self[k] = v
	
	def __setitem__(self, key, value):
		if self._root is None or self._root.get_pos() == self._root_pos:
			# key
			self._f.seek(0, 2)
			key_pos = self._f.tell()
			bon.dump(key, self._f, key_pos)
			
			# value
			self._f.seek(0, 2)
			value_pos = self._f.tell()
			bon.dump(value, self._f, value_pos)
			
			# root
			self._f.seek(0, 2)
			pos = self._f.tell()
			self._root = _SplayDictFileEntry(self._f, pos, key_pos, value_pos, self._root_pos, self._root_pos)
			self._root.write()
			self._f.seek(self._root_pos, 0)
			self._f.write(struct.pack('!Q', self._root.get_pos()))
			return
		
		self.splay(key)
		
		if key == self._root.read_key():
			# new value
			self._f.seek(0, 2)
			new_value_pos = self._f.tell()
			bon.dump(value, self._f, new_value_pos)
			
			# set root.value
			self._root.set_value_pos(new_value_pos)
			self._root.write()
			return
		
		# key
		self._f.seek(0, 2)
		key_pos = self._f.tell()
		bon.dump(key, self._f, key_pos)
		
		# value
		self._f.seek(0, 2)
		value_pos = self._f.tell()
		bon.dump(value, self._f, value_pos)
		
		# n
		self._f.seek(0, 2)
		pos = self._f.tell()
		n = _SplayDictFileEntry(self._f, pos, key_pos, value_pos, self._root_pos, self._root_pos)
		n.write()
		
		if key < self._root.read_key():
			n.set_left_pos(self._root.get_left_pos())
			n.set_right_pos(self._root.get_pos())
			n.write()
			self._root.set_left_pos(self._root_pos)
			self._root.write()
		else:
			n.set_right_pos(self._root.get_right_pos())
			n.set_left_pos(self._root.get_pos())
			n.write()
			self._root.set_right_pos(self._root_pos)
			self._root.write()
		
		# root
		self._root = n
		self._f.seek(self._root_pos, 0)
		self._f.write(struct.pack('!Q', self._root.get_pos()))
	
	def __getitem__(self, key):
		if self._root is None or self._root.get_pos() == self._root_pos:
			raise KeyError('missing item')
		
		self.splay(key)
		
		if key != self._root.read_key():
			raise KeyError('missing item')
		
		return self._root.read_value()
	
	def __delitem__(self, key):
		if self._root is None or self._root.get_pos() == self._root_pos:
			raise KeyError('missing item')
		
		self.splay(key)
		
		if key != self._root.read_key():
			raise KeyError('missing item')
		
		if self._root.get_left_pos() == self._root_pos:
			rr_pos = self._root.get_right_pos()
			rr = _SplayDictFileEntry(self._f, rr_pos, None, None, None, None)
			rr.read()
			self._root = rr
			self._f.seek(self._root_pos, 0)
			self._f.write(struct.pack('!Q', self._root.get_pos()))
		else:
			rr_pos = self._root.get_right_pos()
			rr = _SplayDictFileEntry(self._f, rr_pos, None, None, None, None)
			rr.read()
			x = rr
			rl_pos = self._root.get_left_pos()
			rl = _SplayDictFileEntry(self._f, rl_pos, None, None, None, None)
			rl.read()
			self._root = rl
			self._f.seek(self._root_pos, 0)
			self._f.write(struct.pack('!Q', self._root.get_pos()))
			self.splay(key)
			self._root.set_right_pos(x.get_pos())
			self._root.write()
	
	def splay(self, key):
		t = self._root
		self._header.set_left_pos(self._root_pos)
		self._header.set_right_pos(self._root_pos)
		l = r = self._header
		
		while True:
			tkey = t.read_key()
			
			if key < tkey:
				if t.get_left_pos() == self._root_pos:
					break
				
				tl_pos = t.get_left_pos()
				tl = _SplayDictFileEntry(self._f, tl_pos, None, None, None, None)
				tl.read()
				tl_key = tl.read_key()
				
				if key < tl_key:
					y = tl
					t.set_left_pos(y.get_right_pos())
					t.write()
					y.set_right_pos(t.get_pos())
					y.write()
					t = y
					
					if t.get_left_pos() == self._root_pos:
						break
				
				r.set_left_pos(t.get_pos())
				r.write()
				r = t
				tl_pos = t.get_left_pos()
				tl = _SplayDictFileEntry(self._f, tl_pos, None, None, None, None)
				tl.read()
				t = tl
			elif key > tkey:
				if t.get_right_pos() == self._root_pos:
					break
				
				tr_pos = t.get_right_pos()
				tr = _SplayDictFileEntry(self._f, tr_pos, None, None, None, None)
				tr.read()
				tr_key = tr.read_key()
				
				if key > tr_key:
					y = tr
					t.set_right_pos(y.get_left_pos())
					t.write()
					y.set_left_pos(t.get_pos())
					y.write()
					t = y
					
					if t.get_right_pos() == self._root_pos:
						break
				
				l.set_right_pos(t.get_pos())
				l.write()
				l = t
				tr_pos = t.get_right_pos()
				tr = _SplayDictFileEntry(self._f, tr_pos, None, None, None, None)
				tr.read()
				t = tr
			else:
				break
		
		l.set_right_pos(t.get_left_pos())
		l.write()
		r.set_left_pos(t.get_right_pos())
		r.write()
		t.set_left_pos(self._header.get_right_pos())
		t.set_right_pos(self._header.get_left_pos())
		t.write()
		self._root = t
		self._f.seek(self._root_pos, 0)
		self._f.write(struct.pack('!Q', self._root.get_pos()))
	
	def close(self):
		self._f.flush()
		self._f.close()
		self._f = None

class _SplayDictFileEntry(object):
	def __init__(self, f, pos, key_pos, value_pos, left_pos, right_pos):
		self._f = f
		self._pos = pos
		self._key_pos = key_pos
		self._value_pos = value_pos
		self._left_pos = left_pos
		self._right_pos = right_pos
	
	def set_f(self, f):
		self._f = f
	
	def get_f(self):
		return self._f
	
	def set_pos(self, pos):
		self._pos = pos
	
	def get_pos(self):
		return self._pos
	
	def set_key_pos(self, key_pos):
		self._key_pos = key_pos
	
	def get_key_pos(self):
		return self._key_pos
	
	def set_value_pos(self, value_pos):
		self._value_pos = value_pos
	
	def get_value_pos(self):
		return self._value_pos
	
	def set_left_pos(self, left_pos):
		self._left_pos = left_pos
	
	def get_left_pos(self):
		return self._left_pos
	
	def set_right_pos(self, right_pos):
		self._right_pos = right_pos
	
	def get_right_pos(self):
		return self._right_pos
	
	def write(self):
		self._f.seek(self._pos, 0)
		self._f.write(struct.pack('!QQQQ', self._key_pos, self._value_pos, self._left_pos, self._right_pos))
	
	def read(self):
		self._f.seek(self._pos, 0)
		self._key_pos, self._value_pos, self._left_pos, self._right_pos = struct.unpack('!QQQQ', self._f.read(32))
	
	def read_key(self):
		key = bon.load(self._f, self._key_pos)
		return key
	
	def read_value(self):
		value = bon.load(self._f, self._value_pos)
		return value

def test1():
	t = SplayDictFile('test1.splay', [('m', 't'), ('a', 'a'), ('r', 's'), ('k', 'i'), ('o', 'c')])
	
	print(t['r'])
	del t['r']
	
	try:
		print(t['r'])
	except KeyError:
		print('missing entry "%s"' % 'r')
	
	t.close()

def test2():
	import random
	
	#~ if os.path.exists('test2.splay'):
		#~ os.remove('test2.splay')
	
	t = SplayDictFile('test2.splay')
	d = {i:10000 for i in range(10000)}
	rkeys = d.keys()
	
	random.shuffle(rkeys)
	
	print('< set')
	for k in rkeys:
		t[k] = d[k]
	print('>')
	
	random.shuffle(rkeys)
	
	print('< get')
	for k in rkeys:
		v = t[k]
	print('>')
	
	random.shuffle(rkeys)
	
	print('< get')
	for k in rkeys:
		v = t[k]
	print('>')
	
	random.shuffle(rkeys)
	
	print('< del')
	for k in rkeys:
		del t[k]
	print('>')
	
	t.close()

def test3():
	#~ if os.path.exists('test3.splay'):
		#~ os.remove('test3.splay')
	
	t = SplayDictFile('test3.splay')
	
	t['marko'] = 'tasic'
	t['milan'] = 'vasic'
	t['milos'] = 'prasic'
	print(t['marko'])
	t['marko'] = 'vasic'
	print(t['marko'])
	
	del t['marko']
	
	try: del t['marko']
	except KeyError: print('missing key to del')
	
	try: print(t['marko'])
	except KeyError: print('missing key to get')
	
	t.close()

if __name__ == '__main__':
	test2()
